package hot_100;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

public class 柱状图中最大的矩形 {
    public static void main(String[] args) {

    }

    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        Deque<Integer> deque = new LinkedList<>();
        int left;
        int right;
        int ans = 0;
        deque.addFirst(-1);
        for (int i = 0; i <= n; i++) {
            int h = i < n ? heights[i] : -1;
            while (deque.size() > 1 && heights[deque.getFirst()] >= h) {
                Integer remove = deque.remove();
                right = i;
                left = deque.getFirst();
                ans = Math.max(ans, (right - left - 1) * heights[remove]);
            }
            deque.addFirst(i);
        }
        return ans;
    }
}
